package site.wanjiahao;

import java.util.Comparator;

/**
 * 跳表
 *      存储有序的k-value数据，k作为比较
 *      类似于HashMap查找效率，比HashMap实现简单，采用多级索引，达到以log(n)的效率查找某个元素
 *      并且添加元素按照随机层数添加，而不是下一层元素是上一层元素的两倍。如果添加还要维护元素数量的话
 *      添加删除效率就达不到log(n)，显得没那么必要
 */
public class SkipList<K, V> {

    private int size;

    private Node<K, V> first;

    // 默认最大层数，初始节点的最大层数
    private static final int MAX_LEVEL = 32;

    // 生成随机层数的概率因子
    private static final double P = 0.25;

    // 有效层数，当前存在的层数
    private int level;

    private final Comparator<K> comparator;

    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        first = new Node<>(null, null, MAX_LEVEL);
    }

    public SkipList() {
        this(null);
    }

    public V get(K key) {
        checkKey(key);
        Node<K, V> node = first;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            if (cmp == 0) {
                // 找到值
                return node.nexts[i].value;
            }
        }
        return null;
    }

    public V put(K key, V value) {
        checkKey(key);
        Node<K, V> node = first;
        // 保存当前元素的前驱节点
        Node<K, V>[] prevs = new Node[level];
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            if (cmp == 0) {
                // 找到相同值，覆盖
                V oldValue = node.nexts[i].value;
                node.nexts[i].value = value;
                return oldValue;
            }
            prevs[i] = node;
        }
        // 添加新节点，为其添加前驱，后继
        int newLevel = randomLevel();
        Node<K, V> newNode = new Node<>(key, value, newLevel);
        for (int i = 0; i < newLevel; i++) {
            if (i >= level) {
                // 最上层节点
                first.nexts[i] = newNode;
            } else {
                newNode.nexts[i] = prevs[i].nexts[i];
                prevs[i].nexts[i] = newNode;
            }
        }
        // 计算跳表的最终层大小
        level = Math.max(newLevel, level);
        size++;
        return null;
    }

    public V set(K key, V value) {
        checkKey(key);
        Node<K, V> node = first;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            if (cmp == 0) {
                // 找到相同值，覆盖
                V oldValue = node.nexts[i].value;
                node.nexts[i].value = value;
                return oldValue;
            }
        }
        return null;
    }

    public V remove(K key) {
        checkKey(key);
        Node<K, V> node = first;
        // 保存当前元素的前驱节点
        Node<K, V>[] prevs = new Node[level];
        boolean isExist = false;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            if (cmp == 0) isExist = true;
            prevs[i] = node;
        }
        if (!isExist) return null;
        // 获取当前节点
        Node<K, V> removeNode = node.nexts[0];
        // 修改节点引用关系
        for (int i = 0; i < removeNode.nexts.length; i++) {
            prevs[i].nexts[i] = removeNode.nexts[i];
        }
        int newLevel = 0;
        for (int i = 0; i < level; i++) {
            if (first.nexts[i] == null) continue;
            newLevel++;
        }
        level = newLevel;
        size--;
        return removeNode.value;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return  size == 0;
    }

    private int randomLevel() {
        int level = 1;
        while (Math.random() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    private void checkKey(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key Is Null");
        }
    }

    // 比较
    public int compare(K key1, K key2) {
        if (comparator != null) {
            return comparator.compare(key1, key2);
        }
        return ((Comparable) key1).compareTo(key2);
    }

    // 存储数据的节点对象
    private static class Node<K, V> {

        private K key;

        private V value;

        // 指向下一个的数组元素
        private Node<K, V>[] nexts;

        public Node(K key, V value, int levelSize) {
            this.key = key;
            this.value = value;
            this.nexts = new Node[levelSize];
        }
    }

}
